class GameOfLife {
  int[][] grid;
  ArrayList history;
  int cols;
  int rows;
  int blocksize;
  int hlength;

  GameOfLife(int cols, int rows, int blocksize, int[][] grid) {
    history = new ArrayList();
    this.cols = cols;
    this.rows = rows;
    this.blocksize = blocksize;
    this.grid = grid;
  }

  GameOfLife(int cols, int rows, int blocksize) {
    this.cols = cols;
    this.rows = rows;
    this.blocksize = blocksize;
    initRandom(0.5);
  }

  void initRandom(float prob) {
    history = new ArrayList();
    grid = new int[cols][rows];
    for (int i = 0; i<cols; i++) {
      for (int j =0; j<rows; j++) {
        if (random(1)<prob) {
          grid[i][j] = 1;
        }
        else {
          grid[i][j] = 0;
        }
      }
    }
  }
  
  void step(int mode) {
    
    // add to history
    history.add(new Array2D(grid));
    if (history.size()>hlength) {
      history.remove(0);
    }
    
    int[][] neighbors = getNeighbors(grid);
    int[][] nextGrid = new int[cols][rows];
    
    /* apply rules 
    0: normal game of life
    1: expand
    2: shrink
    3: inverse
    */
    switch (mode) {
    case 0: 
      nextGrid = applyRules(neighbors,1,4,3,3);
     hlength = 4; 
      break;
    case 1: 
      nextGrid = applyRules(neighbors,1,5,3,3);
     hlength = 5; 
      break;
    case 2:
      nextGrid = applyRules(neighbors,2,6,4,4);
      hlength = 1;
      break;
    case 3:
      nextGrid = inverse();
      hlength = 1;
      break;
    default: 
      nextGrid = applyRules(neighbors,1,4,3,3); 
      break;
    }
    
    grid = nextGrid;
  }

  int[][] applyRules(int [][] neighbors, int deathLow, int deathHigh, int birthLow, int birthHigh) {
    int[][] nextGrid = new int[cols][rows];
    for (int i = 0; i<cols; i++) {
      for (int j =0; j<rows; j++) {
        if(grid[i][j] ==1)  {
          if (neighbors[i][j]<= deathLow || neighbors[i][j]>= deathHigh) nextGrid[i][j] = 0;
          else nextGrid[i][j] =1;
        }
        else {
           if (neighbors[i][j] >= birthLow && neighbors[i][j]<= birthHigh) nextGrid[i][j]=1;
           else nextGrid[i][j] = 0;
        }
      }
    }
    return nextGrid;
  }
  
  int[][] inverse()  {
    int[][] nextGrid = new int[cols][rows];
    for(int i =0; i<cols; i++)  {
      for(int j = 0; j<rows; j++)  {
        if(grid[i][j]==1)  nextGrid[i][j] = 0;
        else nextGrid[i][j] = 1;
      }
    }
    return nextGrid;
  }

  void drawGrid() {
    background(0);
    for (int i = 0; i<cols; i++) {
      for (int j =0; j<rows; j++) {
        if (grid[i][j]==1) {
          rect(i*blocksize, j*blocksize, blocksize, blocksize);
        }
      }
    }
  }

  int[][] getNeighbors(int[][] mrRogers) {
    //set neighbors to zero
    int [][] neighbors = new int[cols][rows];
    for (int i = 0; i<cols; i++) {
      for (int j =0; j<rows; j++) {
        neighbors[i][j]=0;
      }
    }
    //add up all neighbors
    for (int i = 0; i<cols; i++) {
      for (int j =0; j<rows; j++) {
        if (mrRogers[i][j] ==1) {
          if (i>0) {
            neighbors[i-1][j]++;
            if (j>0) {
              neighbors[i-1][j-1]++;
            }
            if (j<rows-1) {
              neighbors[i-1][j+1]++;
            }
          }
          if (i < cols-1) {
            neighbors[i+1][j]++;
            if (j>0) {
              neighbors[i+1][j-1]++;
            }
            if (j<rows-1) {
              neighbors[i+1][j+1]++;
            }
          }
          if (j>0) {
            neighbors[i][j-1]++;
          }
          if (j<rows-1) {
            neighbors[i][j+1]++;
          }
        }
      }
    }

    return neighbors;
  }

  int[] parseFrame()  {
    int[] bitmap= new int[cols];
    int bitsum;
    for(int i = 0; i<cols; i++)  {
      bitsum = 0;
      for(int j = 0; j<rows; j++)  {
        bitsum += grid[i][j]<<j;
      }
      bitmap[i] = bitsum;
    }
    return bitmap;
  }
        
        
  boolean isDone() {
    //check if done
    boolean done;
    int[][] oldgrid;
    Array2D oldgridObj;
    for (int h = history.size()-1; h>=0; h--) {
      done = true;
      oldgridObj = (Array2D)history.get(h);
      oldgrid = oldgridObj.getArray();
      for (int i = 0; i<cols; i++) {
        for (int j =0; j<rows; j++) {
          if (grid[i][j]!=oldgrid[i][j]) {
            done = false;
          }
        }
      }
      if (done) {
        return true;
      }
    }

    return false;
  }
}

